package algorithm.graph;

import java.util.*;

public class TopologySort {

    //有向无环图的拓扑排序
    public static List<Node> sortedTopology(Graph graph){
        ArrayList<Node> result = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        HashMap<Node, Integer> map = new HashMap<>();
        for (Node node : graph.nodes.values()) {
            if(node.in == 0)
                queue.add(node);
            else
                map.put(node, node.in);
        }
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            result.add(poll);
            for (Node next : poll.nexts) {
                map.put(next, map.get(next) - 1);
                if(map.get(next) == 0)
                    queue.add(next);
            }
        }
        return result;
    }
}
